package com.niuke;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 3. 宜居星球改造计划
 * 题目描述参考下面链接
 * https://www.bilibili.com/read/cv24268576/
 */
public class NiukeMoni6 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<List<String>> data = new ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            if (line.equals("1")) {
                break;
            }
            String[] arr = line.split(" ");
            data.add(Arrays.asList(arr));
        }

        int row = data.size();
        int col = data.get(0).size();
        int allCount = row * col;
        int yesCount = 0;
        int naCount = 0;

        // 存储YES的位置坐标，很关键，而且增加的时候要在循环结束后一次增加。
        // item List<Integer> 的示例 [0, 0], [0, 1], [2, 0] 等等。
        List<List<Integer>> yesPosition = new ArrayList<>();

        for (int i = 0; i < row; i++) {
            List<String> list = data.get(i);
            for (int j = 0; j < col; j++) {
                if (list.get(j).equalsIgnoreCase("YES")) {
                    List<Integer> item = new ArrayList<>();
                    item.add(i);
                    item.add(j);
                    yesPosition.add(item);
                    yesCount++;
                }
                if (list.get(j).equalsIgnoreCase("NA")) {
                    naCount++;
                }
            }
        }

        int res = 0;
        if (yesCount == 0) { // 没有宜居区，无法拓展
            res = -1;
        } else if (yesCount + naCount == allCount) { // 除了NA区，已经全部宜居了
            res = 0;
        } else {
            int preYesCount = yesCount;

            while (yesCount + naCount < allCount) {
                List<List<Integer>> tmpYesPosition = new ArrayList<>();
                for (int k = 0; k < yesPosition.size(); k++) {
                    List<Integer> item = yesPosition.get(k);
                    System.out.println(Arrays.toString(item.toArray()));
                    Integer i = item.get(0);
                    Integer j = item.get(1);

                    if (j - 1 >= 0 && data.get(i).get(j - 1).equalsIgnoreCase("NO")) {
                        data.get(i).set(j - 1, "YES");
                        yesCount++;
                        List<Integer> newItem = new ArrayList<>();
                        newItem.add(i);
                        newItem.add(j - 1);
                        tmpYesPosition.add(newItem);
                    }
                    if (j + 1 < col && data.get(i).get(j + 1).equalsIgnoreCase("NO")) {
                        data.get(i).set(j + 1, "YES");
                        yesCount++;
                        List<Integer> newItem = new ArrayList<>();
                        newItem.add(i);
                        newItem.add(j + 1);
                        tmpYesPosition.add(newItem);
                    }

                    if (i - 1 >= 0 && data.get(i - 1).get(j).equalsIgnoreCase("NO")) {
                        data.get(i - 1).set(j, "YES");
                        yesCount++;
                        List<Integer> newItem = new ArrayList<>();
                        newItem.add(i - 1);
                        newItem.add(j);
                        tmpYesPosition.add(newItem);
                    }
                    if (i + 1 < row && data.get(i + 1).get(j).equalsIgnoreCase("NO")) {
                        data.get(i + 1).set(j, "YES");
                        yesCount++;
                        List<Integer> newItem = new ArrayList<>();
                        newItem.add(i + 1);
                        newItem.add(j);
                        tmpYesPosition.add(newItem);
                    }

                }

                System.out.println("-----" + preYesCount + " ---- " + yesCount);
                // 如果宜居区数量无法再变化，而while循环宜居区+NA区没达到总区域数量，那说明有被NA区完全包围的NO区
                // 无法改造，只能返回 -1
                if (preYesCount == yesCount) {
                    res = -1;
                    break;
                }

                res++;
                yesPosition.addAll(tmpYesPosition);
                preYesCount = yesCount;
            }
        }
        System.out.println(res);

    }

}
